A key element of many video compression schemes is motion estimation, whereby in a given sequence of video frames, a current video frame is predicted from a previous video frame known as a reference frame. Motion estimation exploits the temporal redundancy between the reference video frame and adjacent video frames to generate an estimated difference between the reference video frame and adjacent video frames. The video compression algorithm may then encode the difference between the reference video frame and the adjacent video frames using less bandwidth than would ordinarily be used without video compression. Another key element of many video compression schemes includes motion detection such as may be utilized within video surveillance systems.
Motion estimation and detection algorithms often divide the reference video frame and each adjacent video frame into smaller groups of pixels known as macroblocks. A search is then conducted, whereby each new macroblock of the current video frame is compared to a macroblock of a pre-determined search area within the reference frame to select the macroblock of the current video frame that exhibits a minimized error measure. In other words, an optimal motion vector is obtained that minimizes the amount of prediction error between the predicted and actual pixel values over all pixels of a motion-compensated region.
To find optimal motion vectors, block prediction errors must first be calculated for each motion vector within the predetermined search range. The amount of prediction error is typically measured using one of a number of algorithms, such as a mean squared error (MSE), also known as a sum of squared differences (SSD) algorithm. Another algorithm for computing prediction error is the mean error algorithm, also known as the sum of absolute differences (SAD) algorithm. Motion vectors that exhibit the least MSE (LSME) or minimized SAD represent the optimal, or best match, motion vector.
The most comprehensive motion estimation algorithm, i.e., full search, obtains optimal motion vectors through an evaluation of every candidate macroblock that exists within the search area. The full search, however, becomes computationally prohibitive especially when operating under real time constraints. Even the inherent parallel processing architectures that are found in field programmable gate arrays (FPGAs) may become overwhelmed due to the large number of computations that are required to implement the full search.
Accordingly, a multitude of search techniques have been developed that limit the number of searches that are performed by reducing the number of candidate positions within the search area that are to be considered during the motion estimation algorithm. Conventional motion estimation algorithms, however, often utilize a much larger search area than is absolutely required. In addition, multiple memory accesses to the same memory space are often performed due to the various consecutive operations that are performed by the motion estimation algorithm. As such, exorbitant bandwidth requirements are imposed upon the local, and/or external, memory resources of the motion estimation structure.
Efforts continue, therefore, to obtain a motion estimation algorithm and associated motion estimation structure that facilitates a significant reduction in the number of memory accesses performed during execution of the motion estimation algorithm. In addition, the motion estimation structure should support a plurality of adaptive motion estimation algorithms that generally operate on pixels from a new macroblock and pixels contained within a search area.